Processes are known for the analysis of deadlocks in an operating system of a machine that consists of searching for a whole unit of execution (called a "thread" by the expert) stopped on a lock (also called a "lock" by the expert), the thread that holds that lock and when that thread is itself waiting for another lock, of going up the chain until it finds a cycle. Such a process for analysis of deadlocks is usually used and this traditional process is described, for example, in "Modern Operating Systems," Tanenbaum 1992 (Prentice-Hall International Editions).
Graph theory is used to solve deadlock problems, and this paper proposes modelling in which the dependency graph of a system is composed of two families of nodes: the processes and the resources that we will transpose to adapt to our application in locks and threads connected by means of arcs according to the following semantics. An arc connecting a thread to a lock means that the thread is stopped waiting for that lock. Inversely, an arc connecting a lock to a thread means that the thread holds that lock, which is therefore temporarily assigned to it. Thus, if the thread T1 is waiting for a lock L1 which is then held by a thread T2 which cannot release that lock L1 because the thread T2 is itself waiting for a lock L2 held by the thread T1, a cycle is formed on the graph and the two threads T1 and T2 are irretrievably stopped, and there is a deadlock. In this example, the cycle formed on the graph is the following: T1.fwdarw.L1.fwdarw.T2.fwdarw.L2.fwdarw.T1.
This type of process can give satisfactory results when it is applied to the analysis of deadlocks in an operating system of a machine that has only one processor, but it shows its limitations and therefore cannot be used effectively with an operating system of a machine that has a symmetrical multiprocessor, even more so when the machine operates in a UNIX environment (trademark of UNIX System Laboratories, Inc.). Indeed, for reasons of performance, an operating system of this type favors the use of "active" locks, i.e., locks which when they are encountered generate an active wait. This active wait is usually justified in a case where a lock is not free but the holder of said lock is active on another processor. In such a case, not waiting actively for a lock which has a very strong probability of being released rather quickly, would be harmful. In addition, exception or interrupt handlers do not have their own execution context, cannot be authorized to go to sleep waiting for a lock and must consequently also wait actively. This can lead to a stack of active waits on a processor, because a thread which is actively waiting for a lock can also be interrupted, while the interrupt handler itself can actively be waiting for a lock.
In searching for a deadlock and analyzing such a situation, the lock stopping the thread is not the one that made it wait (and which has since been released), but the one the interrupt handler was waiting for. Moreover, it can happen that an interrupt handler itself is interrupted for a reason of higher priority, and this therefore then results in a stack that can then reach several stages. If several interrupt handlers in this stack are waiting for a lock, the lock stopping the thread is the one awaited by the higher priority interrupt handler. In that case, the traditional process does not allow a real graph of dependencies to be made or, in particular, a reliable definition of the arcs going from the nodes to the lock-type nodes.